package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-27 15:21
 **/
public class LeetCode34 {

    public int[] searchRange(int[] nums, int target) {


        int low = 0;
        int high = nums.length - 1;
        //记录target出现的次数
        int count = 0;
        //记录target第一次出现的索引
        int index = 0;
        while (low <= high) {
            int avg = (low + high) >> 1;
            if (nums[avg] == target) {
                index = avg;
                count++;
                break;
            } else if (nums[avg] > target) {
                high = avg - 1;
            } else {
                low = avg + 1;
            }
        }
        //count为0说明target不存在，直接返回
        if (count == 0) {
            return new int[]{-1, -1};
        }
        //结果数组
        int[] result = new int[2];
        //复制一份index的值，方便向左右两边蔓延寻找target
        int index2 = index;
        while (index < nums.length - 1 && nums[index + 1] == target) {
            index++;
        }
        result[1] = index;
        while (index2 > 0 && nums[index2 - 1] == target) {
            index2--;
        }
        result[0] = index2;
        return result;
    }

}
